//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 
//
// 有效括号组合需满足：左括号必须以正确的顺序闭合。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 3
//输出：["((()))","(()())","(())()","()(())","()()()"]
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：["()"]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 8 
// 
// Related Topics 字符串 动态规划 回溯 👍 2113 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class _22_GenerateParentheses {
    public static void main(String[] args) {
        int n = 3;
        Solution solution = new _22_GenerateParentheses().new Solution();
        List<String> strings = solution.generateParenthesis(n);
        System.out.println(strings);        // 可以直接显示
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<String> generateParenthesis(int n) {
            if (n == 1) {
                return Arrays.asList("()");
            }
            HashSet<String> set = new HashSet<>();
            for (String str : generateParenthesis(n - 1)) {
                for (int i = 0; i <= str.length() / 2; i++) {
                    set.add(str.substring(0, i) + "()" + str.substring(i, str.length()));
                }
            }
            return new ArrayList<>(set);

        }

        public List<String> generateParenthesis_3(int n) {
            List<String> res = new ArrayList<String>();
            backtrack(res, new StringBuilder(), 0, 0, n);
            return res;
        }

        public void backtrack(List<String> res, StringBuilder sb, int left, int right, int n) {
            if (right == n) {
                res.add(sb.toString());
                return;
            }
            if (left < n) {
                sb.append('(');
                backtrack(res, sb, left + 1, right, n);
                sb.deleteCharAt(sb.length() - 1);
            }
            if (left > right) {
                sb.append(')');
                backtrack(res, sb, left, right + 1, n);
                sb.deleteCharAt(sb.length() - 1);
            }
        }

        public List<String> generateParenthesis_2(int n) {
            List<String> res = new ArrayList<String>();
            digui(res, new char[2 * n], 0);
            return res;
        }

        public void digui(List<String> res, char[] chars, int pos) {
            if (chars.length == pos) {
                if (pan(chars)) {
                    res.add(new String(chars));
                }
            } else {
                chars[pos] = '(';
                digui(res, chars, pos + 1);
                chars[pos] = ')';
                digui(res, chars, pos + 1);
            }
        }

        private boolean pan(char[] chars) {
            int flag = 0;
            for (char ch : chars) {
                if (flag > 0) {
                    return false;
                } else if (ch == '(') {
                    flag--;
                } else if (ch == ')') {
                    flag++;
                }
            }
            if (flag == 0) {
                return true;
            } else {
                return false;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}